package com.kaili.common.tsp;

import com.alibaba.fastjson.JSON;
import com.kaili.common.tsp.ant.ACO;
import com.kaili.common.tsp.simple.ForceSimpleTsp;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 经典TSP旅行商算法
 */
public class TSP {
    private static Logger logger = LoggerFactory.getLogger(TSP.class);


    /**
     * 计算最优路径
     * @param distance
     * @return
     */
    public static String calc(double[][] distance){
        if(distance == null || distance.length<=1){
            return "0";
        }
        int cityNum = distance.length;
        if(cityNum==2){
            return "0,1,0";
        }
        if(cityNum==3){
            return "0,1,2,0";
        }
        if(distance.length<=10){
            return RunForceSimpleTsp(distance);
        }else{
            return RunAnt(distance);
        }
    }

    /**
     * 简单暴力TSP破解算法
     * @param distanceArray
     * @return
     */
    public static String RunForceSimpleTsp(double[][] distance){
        Long start = System.currentTimeMillis();
        logger.info("TSP简单暴力算法-距离矩阵："+JSON.toJSONString(distance));

        ForceSimpleTsp tsp = new ForceSimpleTsp();
        // 1.初始化
        tsp.init(distance);
        // 2.计算最短路径
        tsp.calc(tsp.getCityData(), 1, tsp.getCityNum());

        Long end = System.currentTimeMillis();
        logger.info("TSP简单暴力算法-最佳长度："+tsp.getBestLength());
        logger.info("TSP简单暴力算法-最佳路径："+tsp.getBestTourToString());
        logger.info("TSP简单暴力算法-遍历组合总数："+ tsp.getMaxCount());
        logger.info("TSP简单暴力算法-共耗时:"+(end-start)/1000f);
        return tsp.getBestTourToString();
    }

    /**
     * 蚁群算法
     * @param distance
     * @return
     */
    public static String RunAnt(double[][] distance){
        Long start = System.currentTimeMillis();
        logger.info("TSP蚁群算法-距离矩阵："+JSON.toJSONString(distance));

        double bestLength = 0;
        int[] bestTour = null;
        String bestTourStr = null;
        ACO tsp = null;
        for(int i=0;i<2;i++){
            int cityNum = distance.length;
            int antNum = (int)Math.round(distance.length*1.5);
            tsp = new ACO(cityNum, 6, 200, 1.0f, 5.0f, 0.5f);
            try {
                tsp.init(distance);
            } catch (IOException e) {
                logger.error("TSP蚁群算法异常",e);
            }
            tsp.solve();

            if(bestLength == 0 || tsp.getBestLength()<bestLength){
                bestLength = tsp.getBestLength();
                bestTour = tsp.getBestTour();
            }
        }
        bestTourStr = toString(bestTour);
        Long end = System.currentTimeMillis();
        logger.info("TSP蚁群算法-最佳长度："+bestLength);
        logger.info("TSP蚁群算法-最佳路径："+bestTourStr);
        logger.info("TSP蚁群算法-共耗时:"+(end-start)/1000f);

        return bestTourStr;
    }

    private static String toString(int[] bestTour){
        if(bestTour == null || bestTour.length<=0){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        int current = 0;
        int next = 0;
        sb.append(current).append(",");
        for(int i=0;i<bestTour.length-1;i++){
            next = findNext(current,bestTour);
            sb.append(next).append(",");
            current = next;
        }
        sb.deleteCharAt(sb.length()-1);

        return sb.toString();
    }

    private static int findNext(int current, int[] bestTour){
        int result = 0;
        for(int i=0;i<bestTour.length;i++){
            if(current == bestTour[i]){
                result = bestTour[i+1];
                break;
            }
        }

        return result;
    }

    public static void main(String[] args){
        double[][] distance =
                {{0d,1d,1d,1d},
                        {1d,0d,2d,1.4d},
                        {1d,2d,0d,1.4d},
                        {1d,1.4d,1.4d,0d}};

        calc(distance);
//        int[] test = new int[]{5,3,2,0,1,4,6,7,5};
//        System.out.println(toString(test));
    }
}